#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//不同的子序列
//https://leetcode.cn/problems/distinct-subsequences/submissions/
// class Solution {
// public:
//     int numDistinct(string s, string t) {
//         int n1 = t.size();
//         int n2 = s.size();

//         //vv[i][k]表示
//         //以t字符串[0,i]为子串，在s字符串[0,k]子序列中寻找该子串
//         //如果s[0,k]子序列中存在t[0,i]子串 则将新的结尾字符s[k]加在子序列末尾即可(子序列数并未增加)
//         //否则就在s[0,k-1]子序列中找t[0,i]子串
//         vector<vector<uint64_t>> vv(n1+1,vector<uint64_t>(n2+1));
//         //注意，这里可能出现INT_MAX+INT_MAX的情况 需要考虑 最终情况保证int范围内 但中途计算可能会超出范围

//         //第一行是t字符串的起始位置 每一列为s字符串起始位置
//         //因为我们默认多加一行加一列 相对于字符串前有一个空串
//         //当s字符串为空串时 无法找到t字符串 则为0
//         //当t字符串为空串时，s字符串起始也有空串，所以至少在s字符串中能找到一个t子序列
//         for(int i = 0;i<=n2;++i) vv[0][i] = 1;

//         for(int i = 1;i<=n1;++i)
//             for(int k = 1;k<=n2;++k)
//             {
//                 //vv[i][k-1]中一定存在s子序列中的t子串 所以可以直接加上
//                 vv[i][k] += vv[i][k-1];
//                 //如果是子串结尾相等 则加上新的子串个数
//                 if(t[i-1] == s[k-1]) vv[i][k] += vv[i-1][k-1];
//                 //这里的情况就是 s:abcc 和 t:abc 的区别
//                 //s[0,1,2]可以直接组成t 但是s[0,1,3]也可以 所以是两种情况相加
//             }

//         return vv[n1][n2];
//     }
// };


//通配符匹配
//https://leetcode.cn/problems/wildcard-matching/
// class Solution {
// public:
//     bool isMatch(string s, string p) {
//         int m = s.size(); //原串
//         int n = p.size(); //正则表达式串

//         //vv[i][k] 表示
//         //在s字符串中[0,i] 和p字符串中[0,k] 是否可以相匹配
//         //当s[i] == p[k] 我们只需要保证 s[i-1] 和 p[k-1] 也匹配即可 即vv[i-1][k-1]
//         //当p[k] == '?' 则匹配s[i]的任意一个字符 与上面s[i] == p[k]一样 需要vv[i-1][k-1]
//         //当p[k] == '*' 则需要向s[i-n](n=1,2,3..) 一直遍历
//         //直到遍历到vv[i-n][k] 满足 则从vv[i][k] 到 vv[i-n][k]这段区间的字符全部被 * 匹配
//         //所以*可以匹配一个字符也可以匹配多个字符
//         //其中p[k] == '*'也可以匹配一个空字符 也就是什么也不匹配 当什么也不匹配
//         //则只需要s[0,i]匹配p[0,k-1]即可 也就是vv[i][k-1]
//         //对于vv[i-n][k]从1开始遍历

//         //                            匹配空字符     匹配一个字符      匹配两个字符
//         //即当p[k] == '*'时vv[i][k] = vv[i][k-1] || vv[i-1][k-1] || vv[i-2][k-1] ... ;
//         //这么多情况 需要遍历很多次
//         //vv[i-1][k] = vv[i-1][k-1] || vv[i-2][k-1] || ...
//         //可以发现vv[i-1][k]包揽了除匹配空字符以外的其他情况
//         //所以p[k] == '*'时的转移方程可以转换为 vv[i][k] = vv[i][k-1] || vv[i-1][k];

//         vector<vector<bool>> vv(m+1,vector<bool>(n+1));
//         //初始化
//         //首先vv[0][0]一定是true 因为我们多加了一行和一列避免越界 s和p第一个字符默认都是空字符(实际上没有)
//         //当s串为空时 只能当p串前面字符全部为*时才能匹配空字符 否则都是false
//         //例如 t=" **a*b" s=" " -> s可以匹配t[0][1][2] 从t[3]='a' 开始后面都是false
//         //当p字符串为空时 只能匹配第一个字符 后面都是false
//         //我们只需要初始化s字符串的情况即可
//         vv[0][0] = true;
//         for(int i = 1;i<=n;++i) 
//             if(p[i-1] == '*') vv[0][i] = true;
//             else break; //后面vector默认初始化为false

//         for(int i = 1;i<=m;++i)
//             for(int k = 1;k<=n;++k)
//             {
//                 //优化算法
//                 if(p[k-1] == '*') vv[i][k] = vv[i][k-1] || vv[i-1][k];
//                 else vv[i][k] = ((p[k-1] == s[i-1]) || (p[k-1] == '?')) && vv[i-1][k-1];

//                 //未优化算法
//             //     if(p[k-1] == '*') 
//             //     {
//             //         //匹配空字符
//             //         if(vv[i][k-1]) vv[i][k] = true;
//             //         else //匹配其他字符
//             //         {
//             //             //匹配一个字符 匹配两个字符 一旦匹配到前面已经匹配到的字符串 则停止
//             //             for(int j = i;j>0;--j)
//             //             {
//             //                 if(vv[j-1][k-1])
//             //                 {
//             //                     vv[i][k] = true;
//             //                     break;
//             //                 }
//             //             }
//             //         }
//             //         vv[i][k] = vv[i][k-1] || vv[i-1][k];
//             //     }
//             //     else vv[i][k] = ((p[k-1] == s[i-1]) || (p[k-1] == '?')) && vv[i-1][k-1];
//             // }
        
//         return vv[m][n];
//     }
// };


//正则表达式匹配
//https://leetcode.cn/problems/regular-expression-matching/description/
// class Solution {
// public:
//     bool isMatch(string s, string p) {
//         int m = s.size(); //原串
//         int n = p.size(); //待匹配串

//         vector<vector<bool>> vv(m+1,vector<bool>(n+1));

//         //初始化
//         //m代表行 n代表列
//         //当s为空时，p串中必须是 _*_*_* ... 一旦碰到不匹配的字符后面就都是false 因为_*可以变成空串
//         //s为空串的情况是vv[0][?]
//         //当p为空时，s不为空串时 不能匹配
//         vv[0][0] = true;
//         for(int i = 2;i<=n;i+=2) //一次跳过一个_* 因为多开了一个空间 所以从2开始
//             if(p[i-1] == '*') vv[0][i] = true;
//             else break; //一旦遇到其他字符 则不能组成为匹配空串 跳出 后面都是false

        
//         for(int i = 1;i<=m;++i)
//             for(int k = 1;k<=n;++k)
//             {
//                 //如果p[k-1] == '*'
//                 //当p[k-2] == '.' 时 可以匹配任意多个字符 可以是空串 也可以 任意匹配串
//                 //如果是匹配空串 则只需要vv[i][k-2]匹配即可(p[k-1]识别为空串)
//                 //此时我们只需要匹配到前面已经成功匹配到的串即可
//                 //例如s="abcdef" p="abc.*"
//                 //.*从f开始匹配 一直匹配到s[2] = 'c'字符下 发现前面的abc已经成功匹配
//                 //我们只需要使用.*匹配def即可
//                 //而判断是否匹配 需要判断vv[i-1][k-2] vv[i-2][k-2] vv[i-3][k-2] ...
//                 //转换一下即vv[i-1][k] = vv[i-1][k-2] || vv[i-2][k-2] ...
//                 //vv[i][k] = vv[i][k-2] || vv[i-1][k];
//                 //当p[k-1] == s[i]时 可以匹配当前一个 或前面多个
//                 //要么将_*变成空字符 转而严重p[k-2]和s[i]是否可以匹配 即vv[i][k]
//                 //如果_*可以匹配到字符 那么可以匹配1，2，3，4，5..个
//                 //转换一下即vv[i-1][k]
//                 if(p[k-1] == '*') vv[i][k] = vv[i][k-2] || ((p[k-2] == '.' || p[k-2] == s[i-1]) && vv[i-1][k]);
//                 //如果p[k-1]==s[i-1] 或 p[k-1] == '.'('.'也可以当成空字符)
//                 //此时我们只需要查看前面的字符串是否匹配即可 即 vv[i-1][k-1]
//                 else vv[i][k] = (p[k-1]==s[i-1] || p[k-1] == '.') && vv[i-1][k-1];
//             }

//         return vv[m][n];
//     }
// };




